package src.dp.bag01;

public class no416 {//分割等和子集

    /**
     * 1. dp数组下标含义：容量为 j 的背包，装物品后的总重量是 dp[j]，因为会有装不满的情况
     *      当 dp[target] == target 的时候，背包就装满了。例如dp[7] == 6 就说明没装满
     * 2. 递推公式：dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i] )，每一个元素的数值既是重量，也是价值
     * 3. 初始化数组：dp[0]=1, 即装满背包为0的方法有一种，放0件物品
     * 4. 遍历顺序：先物品后背包，遍历背包时倒序
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        int[] dp = new int[target + 1];

        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
            if (dp[target] == target) return true;  //只要找到一组划分方式就行，所以这里先做一步判断能省点时间
        }

        return dp[target] == target;

    }
}
